package 力扣.树.后序遍历;

import sun.reflect.generics.tree.Tree;

public class 二叉树的最近公共祖先236 {
    private TreeNode ans = null;

    private int postOrder(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return 0;
        }

        // 查看子结点的梳计个数
        int lcnt = postOrder(root.left, p, q);
        int rcnt = postOrder(root.right, p, q);
        //提前判断一下
        if(lcnt == 2 || rcnt == 2){
            return lcnt == 2 ? lcnt : rcnt;
        }
        // 如果左边有一个，右边有一个，那么当前root就是最低公共祖先
        if (lcnt == 1 && rcnt == 1) {
            ans = root;
        } else if (lcnt == 1 || rcnt == 1) {
            // 如果左边找到一个，或者右边找到一个
            // 并且我等于其中某一个结点p|q
            // 那么当前root就是最低公共祖先
            if (root == p || root == q) {
                ans = root;
            }
        }

        // 返回值为以root为根的子树, 统计里面的p,q结点的个数。
        return lcnt + rcnt + ((root == p || root == q) ? 1 : 0);
    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        ans = null;
        postOrder(root, p, q);
        return ans;
    }


    TreeNode ans2 = null;
    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        postDfs(root,p,q);
        return ans2;
    }

    private int postDfs(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null){
            return 0;
        }
        int l = postDfs(root.left, p, q);
        int r = postDfs(root.right, p, q);
        if(l == 1 && r == 1){
            ans2 = root;
        }else if (l == 1 || r == 1){
            if (root == p || root == q){
                ans2 = root;
            }
        }

        return l + r + (root == p || root == q ? 1 : 0);
    }
    public TreeNode lowestCommonAncestor3(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || p == root || q == root) {
            return root;
        }

        TreeNode l = lowestCommonAncestor(root.left, p, q);
        TreeNode r = lowestCommonAncestor(root.right, p, q);

        return l == null ? r : (r == null ? l : root);
    }


    public TreeNode lowestCommonAncestor4(TreeNode root, TreeNode p, TreeNode q) {
           if (root == null || p == null || q == null){
               return null;
           }

           return backDfs(root,p,q) == 2 ? ans3 : null;
    }
    private TreeNode ans3 = null;
    private int backDfs(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null){
            return 0;
        }
        int l1 = backDfs(root.left, p, q);
        int l2 = backDfs(root.right, p, q);
        if (l1 + l2 == 2){
            if (ans3 == null){
                ans3 = root;
            }
            return 2;
        }
        if (root.val == p.val || root.val == q.val){
            if (l1 + l2 == 1){
                ans3 = root;
                return 2;
            }else {
                return 1;
            }
        }
        return l1 + l2;
    }

}
